//
// Created by 抑~风 on 2022/11/29.
//

#include <utility>
#include<fstream>
#include<iostream>
#include<unordered_set>
#include"regexp.h"

class NodeType;

using namespace std;
namespace CWJ {

    string GrammarParser::ROOT_NODE_NAME = "program";
    string GrammarParser::END_SIGN = "$";
    ResASTNode::ResASTNodePtr ResASTNode::EPSILON_NODE = new ResASTNode(NodeType::EPSILON, "EPSILON", "");


    ResASTNode::ResASTNode(const NodeType &nodeType,
                           const string &context,
                           const string &val) : type(nodeType), context(context), val(val) {}

    void ResASTNode::addChild(ResASTNode::ResASTNodePtr son) {
        switch (son->type) {
            case NodeType::OPERATOR:
            case NodeType::TOKEN:
                break;
            case NodeType::IDENT:
                this->identName2child[son->context] = son;
                break;
            default:
                throw runtime_error("ResASTNode::addChild: UnKnown NodeType");
        }
        this->childs.push_back(son);
    }

    ResASTNode::NodeType ResASTNode::getNodeType() const {
        return this->type;
    }

    void ResASTNode::setNodeType(ResASTNode::NodeType nodeType) {
        this->type = nodeType;
    }

    const string &ResASTNode::getContext() const {
        return context;
    }

    void ResASTNode::setContext(const string &context) {
        ResASTNode::context = context;
    }

    const vector<ResASTNode::ResASTNodePtr> &ResASTNode::getChilds() const {
        return childs;
    }

    void ResASTNode::setChilds(const vector<ResASTNodePtr> &childs) {
        ResASTNode::childs = childs;
    }

    void ResASTNode::showResASTNode(ResASTNode::ResASTNodePtr root, string text) {
        unordered_set<ResASTNode::ResASTNodePtr> st;
        ResASTNode::showResASTNode(root, "", st);
    }

    void ResASTNode::showResASTNode(ResASTNode::ResASTNodePtr root, string text,
                                    unordered_set<ResASTNode::ResASTNodePtr> &st) {
        if (!root) return;
        cout << text << (unsigned int) root->getNodeType() << " " << root->getContext() << endl;
        for (const auto &s : root->getChilds()) {
            if (st.count(s) == 1) {
                cout << text + "    " << (unsigned int) s->getNodeType() << " " << s->getContext() << endl;
                continue;
            }
            st.insert(s);
            showResASTNode(s, text + "    ", st);
        }
    }

    const string &ResASTNode::getVal() const {
        return val;
    }

    void ResASTNode::setVal(const string &val) {
        ResASTNode::val = val;
    }

    /** ----------------------------------------------------- */

    unordered_set<GrammarParser::ASTNodePtr> st_show;

    void show(GrammarParser::ASTNodePtr root, string text) {
        if (root == nullptr) return;
        auto childs = root->getChilds();
        auto s = root->getContext();
        cout << text << s.text << " maxTime= " << s.maxTime << " minTime= " << s.minTime << endl;;
        int i = 0;
        for (auto a : childs) {
            if (st_show.count(a.get()) == 0) {
                st_show.insert(a.get());
                show(a.get(), text + "    ");
            } else {
                const auto &c = a->getContext();
                cout << text + "     " << c.text << " maxTime= " << c.maxTime << " minTime= " << c.minTime << endl;
            }
            i++;
        }
    }

    GrammarLever::GrammarLever(string ruleFilePath) : ruleFilePath(std::move(ruleFilePath)) {
        cout << this->ruleFilePath << endl;
    }


    vector<Token<string, string>> GrammarLever::tokenize(string script) {
        this->lever.readRule(this->ruleFilePath);
        return this->lever.tokenize(script);
    }

    const string &GrammarLever::getRuleFilePath() const {
        return ruleFilePath;
    }

    void GrammarLever::setRuleFilePath(const string &ruleFilePath) {
        GrammarLever::ruleFilePath = ruleFilePath;
    }


    GrammarParser::GrammarParser(const string &grfPath) : grfPath(grfPath) {
        this->init();
    }

    void GrammarParser::init() {
        this->readRuleFile(this->grfPath);
    }

    bool GrammarParser::readRuleFile(string path) {

        vector<string> rules;

        this->cUtil.readRule(path, rules);

        for (auto &str : rules) {
            int ind = str.find(':');
            string name = str.substr(0, ind), rule = str.substr(ind + 1);
            this->cUtil.trim(name), this->cUtil.trim(rule);
            this->name2rule[name] = rule;
            this->n2rOrders.push_back(name);
            this->name2tree[name] = new ASTNode(NodeType::OR, {1, 1, name});
        }

        for (const auto &s : this->n2rOrders) {
            this->updateRuleTree(s);
        }
//        for (const auto &s :this->n2rOrders) {
//            st_show.clear();
//            show(this->name2tree[s], "   ");
//        }

        this->rootNode = this->name2tree[GrammarParser::ROOT_NODE_NAME];

        this->caluFirstSet();
        cout << "---------------- firstSets: ------------------------" << endl;
        for (const auto &p:this->firstSets) {

            const auto f = p.first;
            const auto& text = f->getContext().text;
            if(f->getType() == NodeType::TOKEN || text == "AND" || text == "OR")    continue;

            cout << p.first->getContext().text << " : ";
            for (const auto &one : p.second) {
                cout << one << " ";
            }
            cout << endl;
        }


        this->caluFollowSet();
        cout << "---------------- followSets: ------------------------" << endl;
        for (const auto &p:this->followSets) {

            const auto f = p.first;
            const auto& text = f->getContext().text;
            if(f->getType() == NodeType::TOKEN || text == "AND" || text == "OR")    continue;

            cout << p.first->getContext().text << " : ";
            for (const auto &one : p.second) {
                cout << one << " ";
            }
            cout << endl;
        }

        cout << "-----------------------------------------------------" << endl;

//        show(this->rootNode, "    ");

        return true;

    }

    GrammarParser::ResASTNodePtr GrammarParser::parse(const TokenList &tokens) {


        int ind = 0, count = 0;
        unordered_map<ASTNodePtr, int> st;
        return this->parse(tokens, ind, st, this->rootNode, count);
    }

    GrammarParser::ResASTNodePtr
    GrammarParser::parse(const TokenList &tokens, int &ind, unordered_map<GrammarParser::ASTNodePtr, int> &st,
                         GrammarParser::ASTNodePtr node, int &count) {
        count++;
        auto len = tokens.size();
        int oldInd = ind;

        if (ind >= len) return nullptr;

        const auto &token = tokens[ind];
        const auto &tokenType = token.getType();
        const auto &tokenText = token.getConText();

        const auto &nodeType = node->getType();
        const auto &nodeText = node->getContext().text;

        if (nodeText == "functionDeclaration") {
            cout << "";
        }

        ResASTNode::NodeType resType;
        ResASTNodePtr res = new ResASTNode(ResASTNode::NodeType::OPERATOR, "AND", "AND");
        ResASTNodePtr son = nullptr;

        bool isSuccess = false;

        if (nodeType == NodeType::TOKEN) {
            if (tokenType == nodeText) {
                ind++;
                son = new ResASTNode(ResASTNode::NodeType::TOKEN, nodeText, tokenText);
                res->addChild(son);
                isSuccess = true;
            }

        } else {
            if (nodeText == "OR" || nodeText == "AND") {
                resType = ResASTNode::NodeType::OPERATOR;
            } else resType = ResASTNode::NodeType::IDENT;

            res = new ResASTNode(resType, nodeText, nodeText);

            if (nodeType == NodeType::OR) {

                const auto &childs = node->getChilds();
                for (const auto &c:childs) {
                    const auto &num = c->getContext().maxTime;
                    do {
                        auto dddd = c.get();
                        if (st.count(c.get()) && st[c.get()] == ind) {
                            isSuccess = false;
                            break;
                        }
                        st[c.get()] = ind;
                        if ((son = this->parse(tokens, ind, st, c.get(), count))) {
                            isSuccess = true;
                            if (son != ResASTNode::EPSILON_NODE) {
                                res->addChild(son);
                            }
                            st.erase(c.get());
                        }
                        st.erase(c.get());
                        if (!son || son == ResASTNode::EPSILON_NODE)break;
                    } while (num == -1);
                    if (isSuccess) break;
                }
            } else if (nodeType == NodeType::AND) {

                isSuccess = true;
                const auto &childs = node->getChilds();
                for (const auto &c : childs) {

                    auto num = c->getContext().maxTime;
                    do {

                        if (st.count(c.get()) && st[c.get()] == ind) {
                            isSuccess = false;
                            break;
                        }
                        st[c.get()] = ind;

                        if ((son = this->parse(tokens, ind, st, c.get(), count))) {
                            if (son != ResASTNode::EPSILON_NODE) {
                                res->addChild(son);
                            }
                        }
                        st.erase(c.get());
                        if (son == ResASTNode::EPSILON_NODE) {
                            break;
                        }
                        if (!son) {
                            isSuccess = false;
                            break;
                        }
                    } while (num == -1);
                    if (!isSuccess) break;

                }
            }

        }
        if (!isSuccess) {
            if (node->getContext().minTime == 0) return ResASTNode::EPSILON_NODE;
            ind = oldInd;
            return nullptr;
        }

        if (res->getChilds().empty()) {
            cout << "EPSILON_NODE res:" << node->getContext().text << endl;
            return ResASTNode::EPSILON_NODE;
        }

        const auto &text = res->getContext();

        if (res->getChilds().size() == 1 && (text == "AND" || text == "OR")) return res->getChilds().back();
        return res;

    }


    GrammarParser::ASTNodePtr GrammarParser::updateRuleTree(const string &name) {

        const string &rule = this->name2rule[name];
        auto root = this->name2tree[name];

        auto tokens = this->lever.tokenize(rule);

        int start = 0;
        GrammarParser::ASTNodePtr son = nullptr;
        do {
            son = this->dfs_parse_and(tokens, start);
            if (son) {
                root->addChild(son);
            } else break;

            if (start < tokens.size() && tokens[start].getType() == "OR") {
                start++;
            } else break;
        } while (1);

        return root;
    }

    GrammarParser::ASTNodePtr GrammarParser::dfs_parse_and(const TokenList &tokens, int &start) {
        ASTNodePtr root = new ASTNode(NodeType::AND, {1, 1, "AND"});
        ASTNodePtr son = nullptr;
        do {
            son = dfs_parse_prim(tokens, start);
            if (son) {
                root->addChild(son);
            } else break;
        } while (start < tokens.size());

        if (root->getChilds().empty()) return nullptr;
        if (root->getChilds().size() == 1) return root->getChilds().back().get();

        return root;
    }

    GrammarParser::ASTNodePtr GrammarParser::dfs_parse_prim(const TokenList &tokens, int &ind) {
        auto len = tokens.size();

        if (ind >= len) return nullptr;
        const auto &token = tokens[ind];
        auto tokenContext = token.getConText();
        ASTNodePtr res = nullptr;
        this->cUtil.trim(tokenContext);
        if (token.getType() == "TOKEN") {
            res = new ASTNode(NodeType::TOKEN, {1, 1, tokenContext});
            ind++;
        } else if (token.getType() == "IDENT") {
            res = this->name2tree[tokenContext];
            if (res == nullptr) {
                cout << tokenContext << endl;
                throw runtime_error("GrammarParser::dfs_parse_prim: this->name2tree val must not nullptr ");
            }

            ind++;
        } else if (token.getType() == "LPAREN") {
            ind++;
            res = this->dfs_parse_or(tokens, ind);
            if (ind >= tokens.size() || tokens[ind].getType() != "RPAREN") {
                throw runtime_error("GrammarParser::dfs_parse_prim : must ( expression )");
            }
            ind++;
        }

        // TODO 处理重复字符
        if (ind < len && res) {
//           const auto & tmp = res->getContext();
//           if(res->getType() != NodeType::TOKEN && tmp.text != "AND" && tmp.text != "OR" ){
//                auto tt = res;
//                res = new ASTNode (NodeType::AND,{1,1,"AND"});
//                res->addChild(tt);
//            }
            const auto &t = tokens[ind];
            auto context = res->getContext();
            bool isModify = false;
            if (t.getType() == "QUES") {
                context.minTime = 0;
                ind++;
                isModify = true;
            } else if (t.getType() == "PLUS") {
                context.maxTime = -1;
                isModify = true;
                ind++;
            } else if (t.getType() == "STAR") {
                context.minTime = 0;
                context.maxTime = -1;
                isModify = true;
                ind++;
            }
            // 如果是共享的节点，那么就需要在新建的节点中标记次数，以免造成次数污染
            if (isModify && res->getType() != NodeType::TOKEN && context.text != "AND" && context.text != "OR") {
                context.text = "AND";
                auto ptr = new ASTNode(NodeType::AND, context);
                ptr->addChild(res);
                res = ptr;
            } else {
                res->setContext(context);
            }

        }
        return res;
    }

    GrammarParser::ASTNodePtr GrammarParser::dfs_parse_or(const TokenList &tokens, int &ind) {

        auto root = new ASTNode(NodeType::OR, {1, 1, "OR"});

        GrammarParser::ASTNodePtr son = nullptr;
        do {
            son = this->dfs_parse_and(tokens, ind);
            if (son) {
                const auto &ct = son->getContext();
//                if(ct.text == root->getContext().text  && ct.maxTime == ct.minTime && ct.maxTime == 1 ){
//                    for(auto a : son->getChilds()){
//                        root->addChild(a);
//                    }
//                }else {
//                    root->addChild(son);
//                }
                root->addChild(son);
            } else break;

            if (ind < tokens.size() && tokens[ind].getType() == "OR") {
                ind++;
            } else break;
        } while (1);

        if (root->getChilds().empty()) return nullptr;
        if (root->getChilds().size() == 1) return root->getChilds().back().get();

        return root;
    }

    void GrammarParser::caluFirstSet() {
        this->firstSets.clear();
        unordered_set<ASTNodePtr> st;
        while (caluFirstSet(this->rootNode, st));
    }


    void GrammarParser::caluFollowSet() {
        this->followSets.clear();
        unordered_set<ASTNodePtr> st;
        while (caluFollowSet(this->rootNode, st));
    }

    bool GrammarParser::caluFirstSet(GrammarParser::ASTNodePtr root, unordered_set<ASTNodePtr> &st) {

        if (!root) return false;
        if (root->getType() == NodeType::TOKEN) {
            auto &fs = this->caluFiGetFirst(root);
            fs.insert(root->getContext().text);
            return false;
        }

        bool isModify = false;


        FirstSet &firstSet = caluFiGetFirst(root);

        int len = firstSet.size();
        // 先更新子节点
        for (const auto &son : root->getChilds()) {
            if (st.count(son.get())) continue;
            st.insert(son.get());
            isModify |= this->caluFirstSet(son.get(), st);
            st.erase(son.get());
        }
        // 更新当前节点的first集合
        for (const auto &son : root->getChilds()) {
            if (root->getType() == NodeType::OR) {
                calcuFirstSetIsInsert(firstSet, son);
            } else if (root->getType() == NodeType::AND) {
                calcuFirstSetIsInsert(firstSet, son);
                if (son->getContext().minTime > 0) break;
            }
        }

        if (len != firstSet.size()) isModify = true;

        return isModify;
    }

    //该函数的为了较少重复代码
    void GrammarParser::calcuFirstSetIsInsert(GrammarParser::FirstSet &firstSet, const ASTNode::ASTNodePtr &son) {
        if (son->getType() == NodeType::TOKEN) {
            const string &text = son->getContext().text;
            firstSet.insert(text);
        } else {
            const auto &sonFirstSet = firstSets[son.get()];
            firstSet.insert(sonFirstSet.begin(), sonFirstSet.end());
        }
    }

    bool GrammarParser::caluFollowSet(GrammarParser::ASTNodePtr root, unordered_set<ASTNodePtr> &st) {
        if (!root || root->getType() == NodeType::TOKEN) return false;
        bool isModify = false;

        for (const auto &son: root->getChilds()) {
            const auto &ptr = son.get();
            if (st.count(ptr)) continue;
            st.insert(ptr);
            isModify |= this->caluFollowSet(ptr, st);
            st.erase(ptr);
        }

        if (root->getType() == NodeType::AND) {
            const auto &childs = root->getChilds();
            for (size_t i = 0; i < childs.size(); i++) {
                const auto &cur = childs[i];

                if (cur->getType() == NodeType::TOKEN) continue;

                auto &foSet = this->caluFoGetFollow(cur.get());

                int old_len = foSet.size();

                for (size_t j = i + 1; j < childs.size(); j++) {
                    const auto &next = childs[j];
                    if (next->getType() == NodeType::TOKEN) {
                        foSet.insert(next->getContext().text);
                    } else {
                        const auto &nextFiSet = this->caluFiGetFirst(next.get());

                        foSet.insert(nextFiSet.begin(), nextFiSet.end());
                    }

                    if (next->getContext().minTime != 0) break;
                }
                if (old_len != foSet.size()) isModify = true;
            }

            for (int i = childs.size() - 1; i >= 0; i--) {
                const auto cur = childs[i];
                if (cur->getType() != NodeType::TOKEN) {
                    auto &fs = this->caluFoGetFollow(cur.get());
                    if (!fs.count(GrammarParser::END_SIGN)) {
                        fs.insert(GrammarParser::END_SIGN);
                        isModify = true;
                    }
                }
                if (cur->getContext().minTime > 0) break;
            }

        }


        return isModify;
    }

    GrammarParser::FollowSet &GrammarParser::caluFoGetFollow(GrammarParser::ASTNodePtr root) {
        if (!this->followSets.count(root)) {
            this->followSets.insert({root, FollowSet()});
        }
        return this->followSets[root];
    }

    GrammarParser::FirstSet &GrammarParser::caluFiGetFirst(GrammarParser::ASTNodePtr root) {
        if (!this->firstSets.count(root)) {
            this->firstSets[root] = FirstSet();
        }
        return this->firstSets[root];
    }

    GrammarParser::ResASTNodePtr GrammarParser::parseLL1(
            const TokenList &tokens,
            int &ind,
            unordered_map<ASTNodePtr, int> &st,
            GrammarParser::ASTNodePtr node,
            int &count) {

        auto len = tokens.size();
        int oldInd = ind;

        if (ind >= len ){
            if(node->getContext().minTime < 1)  return ResASTNode::EPSILON_NODE;
            return nullptr;
        }

//        cout<<"start :"<< ind <<" "<< tokens[ind].getType() << " " << node->getContext().text << (int)node->getType() << endl;


        const auto &token = tokens[ind];
        const auto &tokenType = token.getType();
        const auto &tokenText = token.getConText();


        const auto &nodeType = node->getType();
        const auto &nodeText = node->getContext().text;

        ResASTNode::NodeType resType;

        ResASTNodePtr res = new ResASTNode(ResASTNode::NodeType::OPERATOR, "AND", "AND");
        ResASTNodePtr son = nullptr;

        const auto &foSet = this->caluFoGetFollow(node);

        bool isSuccess = false;
        if (nodeType == NodeType::TOKEN) {
            if (tokenType == nodeText) {
                ind++;
                son = new ResASTNode(ResASTNode::NodeType::TOKEN, nodeText, tokenText);
                son->setVal(tokenText);
                res->addChild(son);
                isSuccess = true;
            }

        } else {
            if (nodeText == "OR" || nodeText == "AND") {
                resType = ResASTNode::NodeType::OPERATOR;
            } else resType = ResASTNode::NodeType::IDENT;

            res = new ResASTNode(resType, nodeText, nodeText);

            if (nodeType == NodeType::OR) {

                const auto &childs = node->getChilds();
                for (const auto &c:childs) {
                    const auto &num = c->getContext().maxTime;
                    const auto &minNum = c->getContext().minTime;
                    const auto &sonFiSet = this->caluFiGetFirst(c.get());
                    do {

                        if (sonFiSet.count(tokens[ind].getType()) > 0 &&
                            (son = this->parseLL1(tokens, ind, st, c.get(), count))) {
                            isSuccess = true;
                            if (son != ResASTNode::EPSILON_NODE) {
                                if(son->getNodeType() == ResASTNode::NodeType::OPERATOR){
                                    for(auto s : son->getChilds()){
                                        res->addChild(s);
                                    }
                                }else {
                                    res->addChild(son);
                                }
                            }
                        }
                        if (!son || son == ResASTNode::EPSILON_NODE)break;

                        son = nullptr;

                    } while (num == -1 && ind < len);

                    if (ind >= len) isSuccess = true;
                    if (isSuccess) break;
                    else  if (minNum == 0 && foSet.count(tokens[ind].getType())) {
                        isSuccess = true;
                        break;
                    }

//                    cout<<c->getContext().text<<endl;

                }
            } else if (nodeType == NodeType::AND) {
                isSuccess = true;
                const auto &childs = node->getChilds();
                bool isEnd = false;
                for (const auto &c : childs) {
                    auto num = c->getContext().maxTime;
                    do {
                        if ((son = this->parseLL1(tokens, ind, st, c.get(), count))) {
                            if (son != ResASTNode::EPSILON_NODE) {
                                if(son->getNodeType() == ResASTNode::NodeType::OPERATOR){
                                    for(auto s : son->getChilds()){
                                        res->addChild(s);
                                    }
                                }else {
                                    res->addChild(son);
                                }
                            }
                        }
                        if (son == ResASTNode::EPSILON_NODE) {
                            break;
                        }
                        if (!son) {
                            isSuccess = false;
//                            cout<<"AND false"<<endl;
                            break;
                        }
                        son = nullptr;



                        // 这里不需要进行边界判断ind < len,因为其在这个循环中不会使用到ind,如果这个边界没有被满足，那么就会返回nullptr
                        // 那么就会自动跳出循环
                    } while (num == -1);
                    if (!isSuccess) break;
                }
            }

        }
        if (!isSuccess) {
            ind = oldInd;
            if (node->getContext().minTime == 0 ) {
//               if(ind<len) cout <<"11return epsilon : "<< ind <<" "<< tokens[ind].getType() << " " << node->getContext().text << (int)node->getType()<<" " <<node << endl;
                return ResASTNode::EPSILON_NODE;
            }

//            if(ind<len)cout <<"fail: "<< ind <<" "<< tokens[ind].getType() << " " << node->getContext().text << (int)node->getType() << endl;
            return nullptr;
//            throw runtime_error("parseLL1 match error : exist backtracking  ");
        }

        if (res->getChilds().empty()) {
            ind = oldInd;
//            cout <<"return epsilon : "<< ind <<" "<< tokens[ind].getType() << " " << node->getContext().text << (int)node->getType()<<" " <<node << endl;
            return ResASTNode::EPSILON_NODE;
        }

        const auto &text = res->getContext();
//        cout<<"success :";
//        if(ind<len)cout << ind <<" "<< tokens[ind].getType() << " " ;
//        cout<< node->getContext().text << (int)node->getType() << endl;
        if (res->getChilds().size() == 1 && (text == "AND" || text == "OR")) return res->getChilds().back();
        return res;

    }

    GrammarParser::ResASTNodePtr GrammarParser::parseLL1(const TokenList &tokens) {
        int ind = 0, count = 0;
        unordered_map<ASTNodePtr, int> st;
        return this->parseLL1(tokens, ind, st, this->rootNode, count);
    }


}